home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / hamradio / dspmorse.zip / FFTMORSE.DOC < prev    next >
Text File  |  1992-05-01  |  20KB  |  378 lines

  1. /* Warning! This documentation contains extended characters! */
  2.  
  3. Program: FFTMORSE.ZIP (freeware)
  4. Date:    1 May 1992
  5. Version: 1.0
  6. Files:   FFTMORSE.EXE
  7.          FFTMORSE.DOC
  8.          FFTMORSE.C
  9.  
  10. Turbo-C flags: -mt -1 -d -f- -A -K -G -O -w
  11.  
  12. Copyright (c) 1992 François Jalbert (jalbert@IRO.UMontreal.CA)
  13.  
  14. A few more copyright notices so everybody is happy:
  15.  
  16.   Sound-Blaster (c) 1989-1991 Creative Labs Inc
  17.   Turbo-C 2.0 (c) 1988 Borland International
  18.   Sound-Blaster C Library BLAST13 (c) 1991 Joel Lucsy
  19.   LZEXE 0.91 (c) 1989 Fabrice Bellard
  20.  
  21.  
  22. Description:
  23. ───────────
  24.  
  25. This program will decode morse code coming from your short-wave receiver. 
  26. Extensive attention as been paid to efficiency and to robustness. With a 286/12 
  27. and a Sound-Blaster 2.0, it operates at about 10kHz and gives me 100% accuracy 
  28. on good quality signals and good quality (!) key operators. It does not require 
  29. any special hardware or short-wave receiver capabilities; a simple dynamic 
  30. microphone hooked to your Sound-Blaster will do the job. 
  31.  
  32.  
  33. Justification:
  34. ─────────────
  35.  
  36. Since I was given an old 1950 tube short-wave receiver about a year ago to heat 
  37. up my room in winter, I had been dreaming about being able to understand the 
  38. morse code I could pick up around the 40 and 80 meter bands. I quickly learned 
  39. the morse code, but I found that decoding was not feasible in practice. First, 
  40. I lacked speed. Second, I had to concentrate most of the time on my short-wave 
  41. receiver since the signals keep drifting back and forth, therefore requiring 
  42. constant fine tuning adjustments from my part. There is simply no time left to 
  43. decode any morse code! 
  44.  
  45. My dream finally became possible when I bought a Sound-Blaster 2.0 last month. 
  46. Using its Digital Signal Processing (DSP) unit, it is possible with a micro-
  47. phone (or a direct line) to digitize an analog signal at a rate of up to 15KHz. 
  48. That is more than enough for the task at hand. 
  49.  
  50. Unfortunately, the Sound-Blaster comes with no information on how to interface 
  51. with it in assembly or in some higher-level language. I gave SIMTEL a shot and 
  52. got lucky; I located the Sound-Blaster C library BLAST13 of Mr. Joel Lucsy. It 
  53. took only a few minutes to disassemble its DSP routines and get a basic under-
  54. standing of what's going on. Direct operation is indeed trivial. 
  55.  
  56. Nevertheless, I decided not to use assembly for this little project since this 
  57. is invariably time consuming. Instead, I used C and the library I had found. If 
  58. worse came to worse, I might stick in a couple of assembly functions, but this 
  59. turned out not to be necessary. I must express my gratitude to Mr. Lucsy for 
  60. opening the world of the Sound-Blaster to all of us. 
  61.  
  62. Another important problem is the low quality of signal one must typically face. 
  63. There is an omnipresent strong background noise, the morse signal comes and 
  64. goes, its frequency changes all the time, and you usually get two or three 
  65. different morse signals (of different tone frequency) for a given tuning setup. 
  66. Basic experimentation confirmed what I had suspected all along. It would be 
  67. necessary to perform a Fourier analysis in order to filter out noise and 
  68. undesirable signals. It better be a fast one too! 
  69.  
  70. If all goes well, I will end up with a series of tone quantified in terms of 
  71. duration. It should be relatively easy to program a simple learning algorithm 
  72. which would quickly get accustomed to a given key operator. Automatic decoding 
  73. would be snap from that point on. This last step should be very dependent on 
  74. the operator and his regularity. I bet some pretty fancy keys are in use today. 
  75. They probably insure a good uniformity of the morse code sent. If that's indeed 
  76. the case, interpreting should not be very difficult. 
  77.  
  78. There is no program performing the function of FFTMORSE available at SIMTEL as 
  79. of now. The closest thing I could find involved building some electronic 
  80. interface between the short-wave and the serial port of the computer. Close but 
  81. not good enough for me. I wanted something simpler using current technology. 
  82. Therefore, I believe that this project was justified and I am happy to hereby 
  83. contribute to the public domain. 
  84.  
  85. This program has been tested on VGA only. It should run on mono. It has been 
  86. tested with a Sound-Blaster 2.0 only. It should work with the 1.0 and 1.5 
  87. versions. I also assume that the Sound-Blaster Pro is hardware backward 
  88. compatible. Finally, it has been tested on a 12MHz 286 only. It should run on 
  89. faster machines as well and it does use 286 (186?) or above instructions. In 
  90. fact, the Sound-Blaster card itself is likely to be the cause of any 
  91. difficulties you may experience with a 486/33 or a 486/50! 
  92.  
  93. Feel free to pass along and share copies of my work. If you have any comments 
  94. or suggestions, I would be very happy to hear from you. My internet e-mail 
  95. address can be found at the top of this brief document. 
  96.  
  97.  
  98. Functional Description:
  99. ──────────────────────
  100.  
  101. The main functions of this program are:
  102.  
  103.  ■ Initialization function begin();
  104.  ■ Fast Fourier transform function FFT();
  105.  ■ Tone detection function FFT2tone();
  106.  ■ Learning function learn();
  107.  ■ Morse interpreter function tone2morse();
  108.  ■ Text interpreter function morse2text();
  109.  ■ Keyboard handling function handlekey();
  110.  ■ The usual main function main();
  111.  
  112. and I would like to briefly introduce them so you will have a better under-
  113. standing of what my program does, does not, and what the various interactive 
  114. functions available do. 
  115.  
  116. The initialization function clears the screen, initializes the Sound-Blaster 
  117. DSP, detects whether a mono or a color card is present by the video mode 
  118. currently in use (7=mono), and draws the various screen elements.
  119.  
  120. The fast Fourier transform function is quite complex and warrants a section on 
  121. its own which you will find below. All I want to say at this stage is that 32 
  122. values are fed from the Sound-Blaster as fast as it can deliver them. The FFT 
  123. computation then takes place and this results in 15 short integers in the range 
  124. [0,32] representing the activity in 15 frequency ranges. 
  125.  
  126. It is also possible to read 64 values from the Sound-Blaster and to discard 
  127. every other one. This is called a mixture ratio of 1:2. You can also read 96 
  128. values and discard 2 of them out of 3; a mixture ratio of 1:3. And so forth. 
  129. A non trivial mixture ratio is sometimes desirable for two reasons. 
  130.  
  131. First of all, as we saw above, information is read from the Sound-Blaster in 
  132. short bursts, with a pause in between to perform the FFT calculations. This 
  133. irregularity somehow introduces noise in the Sound-Blaster output. A mixture 
  134. ratio of 3 or 4 totally eliminates this noise since data read is more regularly 
  135. spaced in time. 
  136.  
  137. Second, varying the mixture ratio allows you to control where one particular 
  138. tone will show up in the frequency display. The usual gaussian curve moves up 
  139. and down as the mixture is changed. This also makes it possible for you to 
  140. better isolate some morse tone buried under other ones of different frequency. 
  141.  
  142. The tone detection function turned out fairly straightforward. I wanted 
  143. something which would detect the presence of a tone, presence usually taking 
  144. the form of a gaussian curve in the frequencies displayed. I decided out of 
  145. simplicity not to try to be clever and to automatically detect the presence of 
  146. such a dome. This seemed too problematic when one considers the level of noise 
  147. often present and the multiple domes also occasionally encountered. 
  148.  
  149. Instead, I let the user select which frequency area he considers to be the 
  150. relevant one. Such a relevant frequency area is made up of 5 consecutive 
  151. frequencies, and this area will determine the presence or absence of a morse 
  152. tone. This can, of course, be adjusted at all time by the user. 
  153.  
  154. Activity detection is performed by first computing the average activity of all 
  155. 15 frequencies extracted. This is used to get an idea of the uniform noise 
  156. level. The total activity in the relevant frequency area is then examined and 
  157. if this activity is at least 5 above what the average would call for, the 
  158. relevant frequency area is considered active at that time. This value of 5 is 
  159. arbitrary, but seems to work well in practice. However, it is recommended to 
  160. adjust the audio level of your short-wave receiver as low as possible at all 
  161. time, in order to keep the confusing background noise to a minimum. 
  162.  
  163. I also discovered that activity in the relevant frequency area may vary 
  164. somewhat, even though a continuous tone is present. This seems to stem from the 
  165. nature of the Fourier transform. Therefore, I added a short term memory to my 
  166. tone detection algorithm. A tone is considered present is at least one of the 
  167. last 4 cycles turned out active as defined above. Once more, this seems to work 
  168. very well in practice. 
  169.  
  170. The learning function collects a total of 8 dots and 8 dashes, and computes an 
  171. average duration for each of them. This is used to decode tones into morse 
  172. basic elements. To differentiate between a dot and a tone initially, this 
  173. function first waits until it encounters a dot-dash or dash-dot pair. This is 
  174. easily detected by comparing the duration of each consecutive pair. Once such a 
  175. significative pair is detected, the statistics can be compiled.
  176.  
  177. What happens if you switch station and the new key operator is somewhat faster 
  178. or slower than the previous one? I decided once again not to try to be smart 
  179. and to detect that occurrence automatically. If you think about it, you will 
  180. find that this can get quite tricky in the presence of noise and a few ghost 
  181. tones. Instead, you have to manually indicate to the program the need to 
  182. recompile new key operator statistics. 
  183.  
  184. The morse interpreter function receives a series of tone presence/absence and 
  185. their duration. It is a simple thing to compare these durations with the 
  186. statistics compiled for the current key operator, and to deduce dots and 
  187. dashes. The statistics are also updated since the current key operator may be 
  188. warming up and may be slowly picking up speed! 
  189.  
  190. The text interpreter function receives a series of dots, dashes, and spaces. 
  191. These are easily translated into their equivalent ASCII values and displayed in 
  192. a window on the left. I used the international morse code as I found it in my 
  193. dictionary. I was surprised to see that it includes a few accentuated letters. 
  194. So be it, their support won't do any harm.
  195.  
  196. The keyboard handling function is called only if a key pressed has been 
  197. detected. The appropriate parameters are adjusted and there's really nothing to 
  198. this function otherwise.
  199.  
  200. The main function is made of two loops embodied one into the other. The most 
  201. inner one performs KCHECK cycles each involving 32 sampled values before 
  202. allowing the keyboard to be checked for a key pressed. The outer loop operates 
  203. SCHECK times before allowing the update of some secondary information (key 
  204. operator statistics and actual sampling rate) on the screen. These loops insure 
  205. that most of the CPU time is spent on the main task. 
  206.  
  207. So here you have it, a complete informal description of what the program does 
  208. and how it does it. I do admit that this remains a little bit crude, but I just 
  209. had one week to spend on this. Although I do not plan on releasing future 
  210. versions, I'll be happy to hear from you. So please do not hesitate to write!
  211.  
  212.  
  213. FFT Technical Notes:
  214. ───────────────────
  215.  
  216. The most complex element of this small project is by far the fast Fourier 
  217. transform algorithm I had to develop. My first prototype was a simple direct 
  218. application of discrete Fourier transforms. I used the 287 for the floating 
  219. point operations, but the resulting code turned out too slow on my 286/12. A 
  220. long integer version also proved too slow. Before jumping into assembly, I 
  221. decided to give a short integer version a try. It turned out not too bad. Here 
  222. is first of all the background information concerning it. 
  223.  
  224. The Fourier polynomial on an interval [0,2π] divided into 2N segments reads: 
  225.  
  226.                     a0   N-1 ┌                       ┐   aN 
  227.              p(x) = ── +  Σ  │ a cos(lx) + b sin(lx) │ + ── cos(Nx)
  228.                      2   l=1 └  l           l        ┘    2 
  229.  
  230. I use 2N intervals since this even number results into more symmetry for the 
  231. trigonometric values involved. The underlying knots are:
  232.  
  233.                              π 
  234.                          x = ─ k      for k=0,...,2N-1 
  235.                           k  N 
  236.  
  237. The usual analysis will yield the following discrete Fourier coefficients:
  238.  
  239.                     1 2N-1          ┌ π    ┐
  240.                 a = ─   Σ  f(x ) cos│ ─ kl │      for l=0,...,N
  241.                  l  N  k=0    k     └ N    ┘
  242.  
  243.                     1 2N-1          ┌ π    ┐
  244.                 b = ─   Σ  f(x ) sin│ ─ kl │      for l=1,...,N-1
  245.                  l  N  k=0    k     └ N    ┘
  246.  
  247. I will immediately discard a  and a  and these shall not be computed.
  248.                             0      N
  249.  
  250. It is obvious that some look-up tables can be computed in advance to speed up 
  251. things later on. We therefore have the following definitions: 
  252.  
  253.                       1
  254.                   f = ─ f(x )                 for k=0,...,2N-1
  255.                    k  N    k
  256.  
  257.                          ┌ π   ┐
  258.                   c = cos│ ─ k │ = cos(x )    for k=0,...,2N-1
  259.                    k     └ N   ┘        k
  260.  
  261.                          ┌ π   ┐
  262.                   s = sin│ ─ k │ = sin(x )    for k=0,...,2N-1
  263.                    k     └ N   ┘        k
  264.  
  265. The quantities we want to compute can now be restated as:
  266.  
  267.                       2N-1
  268.                   a =   Σ  f  c               for l=1,...,N
  269.                    l   k=0  k  (kl)%(2N)
  270.  
  271.                       2N-1
  272.                   b =   Σ  f  s               for l=1,...,N
  273.                    l   k=0  k  (kl)%(2N)
  274.  
  275. where % stands for the usual modulo operator.
  276.  
  277. This is exactly what the first version of my short integer Fourier transform 
  278. did. In order to avoid short integer overflows and to get the maximum number 
  279. of bits of precision in the final result, I did make a few scaling changes: 
  280.  
  281. 1) The values coming from the Sound-Blaster lie in the interval [0,255] and I 
  282.    rescaled them into [-128,127] in order to better repartition the bits. This 
  283.    helped tremendously. 
  284.  
  285. 2) I didn't include 1/N in the f 's involved.
  286.                                 k
  287.  
  288. 3) I multiplied the s 's and the c 's by 16 to get 4 bits of integer precision.
  289.                      k            k
  290.  
  291. 4) The resulting a 's and b 's are divided by 2048 to bring them into [-16,16].
  292.                   l        l
  293.  
  294. 5) The final results are │ a │ + │ b │ which all belong to the interval [0,32].
  295.                             l       l
  296.  
  297. This computation of Fourier coefficients implies only short integer operations, 
  298. half of which are unfortunately multiplications. This first attempt worked 
  299. reasonably fast, but not fast enough. I wanted to have a very good sampling 
  300. rate before getting into the next steps. This will be a long chain and if the 
  301. starting information is scarce and/or of poor quality, I fear that this may 
  302. hurt me later on. 
  303.  
  304. I tried to cheat a little bit and to combine the Fourier coefficients as in:
  305.  
  306.                2N-1    ┌                        ┐
  307.            d =   Σ  f  │ c         + s          │      for l=1,...,N
  308.             l   k=0  k └  (kl)%(2N)   (kl)%(2N) ┘
  309.  
  310. This would cut the operation count by two, but I found the results not so good. 
  311. This is equivalent to using a different mathematical basis, which is not 
  312. orthogonal anymore, and which probably has a different physical interpretation 
  313. than the usual frequency response interpretation I wanted. So I reluctantly 
  314. went back to the previous separate Fourier coefficients approach. 
  315.  
  316. I looked into the classical Fast Fourier Transform algorithm, but it offered 
  317. only an O(N log N) complexity versus the current O(N*N) count. Not good enough 
  318. to warrant the trouble, I thought. Plus it would involve a lot of playing with 
  319. array indices, arrays I would rather eliminate altogether... 
  320.  
  321. So I expanded the equations for the Fourier coefficients and spent two days (!) 
  322. rearranging terms, finding common sub-expressions, and gradually incorporating 
  323. that into my code. There was a lot of repetition present, and it obeyed the 
  324. intuitively expected regularity rules. I eventually came up with a tight and 
  325. super fast 32 knots version. It is one to two orders of magnitude faster than 
  326. my first attempt! Not a single array is involved in the middle computations, 
  327. but a lot of short integer temporary variables are required. I am sampling not 
  328. to far from the maximum rate supported by my Sound-Blaster. No doubt any 386 
  329. and 486 will be working at maximum sampling rate with still plenty of time to 
  330. spare. 
  331.  
  332. The courageous ones will take a look at function FFT() in my program. Please 
  333. feel free to double check everything and to report to me ASAP!!! 
  334.  
  335.  
  336. Operation:
  337. ─────────
  338.  
  339. There are no command line parameters, just type FFTMORSE and there you are. 
  340. However, a number of keys are in use from within the program.
  341.  
  342. <space> This toggles FFT on and off. Morse decoding requires the FFT option to 
  343.         be active. This switch was added to make it possible for you to get a 
  344.         very good sampling rate while tuning your short-wave receiver. A high 
  345.         sampling rate improves the quality of the sound coming out ot the 
  346.         Sound-Blaster. Once you have an interesting station, you should toggle 
  347.         FFT back on to start decoding the incoming morse code. On fast 
  348.         computers, this key is probably not very useful.
  349.  
  350. <+> These change the mixture ratio by throwing away samples every now and then. 
  351. <-> This makes it possible to move the signal up and down the FFT display until 
  352.     it is located more or less in the middle. This is where I suspect the 
  353.     Fourier analysis is at its best. These are only operational if the FFT is 
  354.     enabled. Too high a value (say 10) is not desirable since this throws away 
  355.     too much information and slows down everything since the Sound-Blaster can 
  356.     only supply 15Kb of information per second at best.
  357.  
  358. <*> Used to toggle learn mode where the program will accumulate statistics 
  359.     about typical dot and dash lengths. After a while, morse decoding will 
  360.     resume on its own. Use this whenever you switch station or after 
  361.     encountering a lot of noise which may have confused the program. Indeed, 
  362.     the program continuously slowly adapts to changes of rhythm in the morse 
  363.     code received.
  364.     
  365. <Up Arrow>   Used to move the frequency window of interest up and down. This is 
  366. <Shift Up>   very useful in case the current tone frequency is not exactly in 
  367. <Shift 5>    the middle of the FFT display, or if several morse signals of 
  368. <Shift Down> different tone frequencies are active at the same time. In the 
  369. <Down Arrow> latter case, you can isolate the signal of interest for you.
  370.  
  371. <Esc> Exit the program.
  372.  
  373. Note: In order to avoid spending too much time asking the BIOS if a key has 
  374.       been pressed, key pressed checks are performed only every once in a 
  375.       while. On my 286/12, that's about once every two seconds. So do not 
  376.       expect immediate crisp response following your keyboard entries. Response 
  377.       time also increases with the mixture ratio (keys <+> and <-> above). 
  378.